# 二叉搜索树中的众数：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right


# 说是一道简单题，但是我却想了很久~~ 还要看视频思路才能做出来~~
# 绕的地方就是，1.  三个变量计数的时候，一定是判断当前元素是否能添加到结果集（不是判断preNum）
# 2. 对边界（第一个元素的处理），还有 变量的初始化的值设置。 当按照 1. 的思路来，就清晰了，一定是判断当前元素是否添加到结果集
# 我的写法：
class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        """
            这道题相当于求众数， 而，二叉搜索树的 中序遍历，恰好是增序排序的。
            只要在中序时， 统计出，出现最多的就可以了
            
            # 思路过程
            1. curCnt： 首先遍历时， 需要记录元素出现的次数， 
            2. maxCnt： 当前位置， 最大的遍历次数（当后面的遍历次数大于前面时，要进行删除加入结果集的元素）
            3. preNum： 还需要记住前面一个出现的元素， 这样才能累计和进行判断
        """
        rst = []
        curCnt, maxCnt, preNum = 0, 0, None
        def inOrder(node):
            nonlocal curCnt
            nonlocal maxCnt
            nonlocal preNum
            if not node: return

            inOrder(node.left)
            # 1. 先更新当前curCont
            if node.val == preNum:
                curCnt += 1
            else:
                curCnt = 1
            
            # 2. 是否添加到结果集
            if curCnt == maxCnt:
                rst.append(node.val)
            elif curCnt > maxCnt:
                maxCnt = curCnt
                # 删除当前结果集中的元素，他们不是计数最大的了
                rst.clear()
                rst.append(node.val)

            # 3. preNum 更新为当前元素
            preNum = node.val

            inOrder(node.right)

        inOrder(root)
        return rst


# 可以优化 preNum的写法， 和上面改动很小。 只有preNum 不等于当前值的时候，才去更新
class Solution:
    def findMode(self, root: TreeNode) -> List[int]:
        """
            这道题相当于求众数， 而，二叉搜索树的 中序遍历，恰好是增序排序的。
            只要在中序时， 统计出，出现最多的就可以了
            
            # 思路过程
            1. curCnt： 首先遍历时， 需要记录元素出现的次数， 
            2. maxCnt： 当前位置， 最大的遍历次数（当后面的遍历次数大于前面时，要进行删除加入结果集的元素）
            3. preNum： 还需要记住前面一个出现的元素， 这样才能累计和进行判断
        """
        rst = []
        curCnt, maxCnt, preNum = 0, 0, None
        def inOrder(node):
            nonlocal curCnt
            nonlocal maxCnt
            nonlocal preNum
            if not node: return

            inOrder(node.left)
            # 1. 先更新当前curCont
            if node.val == preNum:
                curCnt += 1
            else:
                # 3. preNum 更新为当前元素
                preNum = node.val
                curCnt = 1
            
            # 2. 是否添加到结果集
            if curCnt == maxCnt:
                rst.append(node.val)
            elif curCnt > maxCnt:
                maxCnt = curCnt
                # 删除当前结果集中的元素，他们不是计数最大的了
                rst.clear()
                rst.append(node.val)

            inOrder(node.right)

        inOrder(root)
        return rst